package com.lfg.leetcode.leetcode100;

import com.lfg.leetcode.leetcode0.ListNode;
import com.lfg.leetcode.leetcode0.TreeNode;

public class No109sortedListToBST {

    public static void main(String[] args) {
        TreeNode ret = sortedListToBST(ListNode.deserialize("[1,2,3,4,5,6,7,8,9]"));
        System.out.println("[" + ret + "]");
    }

    public static TreeNode sortedListToBST(ListNode head) {
        int length = 0;
        ListNode listNode = head;

        while (listNode != null) {
            length++;
            listNode = listNode.next;
        }
        ListNode[] list = new ListNode[length];
        listNode = head;
        for (int i = 0; i < length && null != listNode; i++) {
            list[i] = listNode;
            listNode = listNode.next;
        }

        return sortedListToBST(list, 0, length - 1);
    }

    public static TreeNode sortedListToBST(ListNode[] head, int sIndex, int eIndex) {
        if (null == head || sIndex > eIndex || eIndex >= head.length || sIndex < 0) {
            return null;
        }
        if (sIndex == eIndex) {
            return new TreeNode(head[sIndex].val);
        }
        int total = eIndex + sIndex;
        int mid = total / 2;
        if ((total & 1) == 1) {
            mid++;
        }
        TreeNode ret = new TreeNode(head[mid].val);
        ret.left = sortedListToBST(head, sIndex, mid - 1);
        ret.right = sortedListToBST(head, mid + 1, eIndex);
        return ret;
    }

    public static TreeNode sortedListToBST2(ListNode head) {
        int length = 0;
        ListNode listNode = head;
        while (listNode != null) {
            length++;
            listNode = listNode.next;
        }
        return sortedListToBST2(head, length);
    }

    public static TreeNode sortedListToBST2(ListNode head, int length) {
        if (length == 1) {
            return new TreeNode(head.val);
        }
        int mid = length / 2;
        if ((length & 1) == 1) {
            mid++;
        }
        int index = 1;
        ListNode listNode = head;
        while (listNode != null) {
            if (index == mid) {
                break;
            }
            index++;
            listNode = listNode.next;
        }
        if (listNode == null) {
            return null;
        }
        TreeNode ret = new TreeNode(listNode.val);
        ret.left = sortedListToBST2(head, mid - 1);
        ret.right = sortedListToBST2(listNode.next, length - mid);
        return ret;
    }
}
